package base.Chapter00_Structures.C03_LinkList;

/**
 * 链表面试题
 * 1, 单向链表
 * 2, 双向链表
 * 3, 删除单向链表中的指定值
 * 4, 删除双向链表中的指定值
 */
public class C01_CaseInterview {
    /**
     * 作用: 单向链表反转
     *
     * @param headNode 头节点
     * @return 反转之后的头节点
     */
    public static <T> SingleLinkedListNode<T> reverse(SingleLinkedListNode<T> headNode) {
        //0, 设置初始环境
        SingleLinkedListNode preNode = null;    // 设置preNode
        SingleLinkedListNode currentNode = headNode; // 设置当前Node

        while (currentNode != null) {
            //1, 记录环境
            SingleLinkedListNode nextNode = currentNode.getNextNode();
            //2, 反转¬
            currentNode.setNextNode(preNode);
            //3, 设置下一轮新环境
            preNode = currentNode; // currentNode使用完
            currentNode = nextNode; //
        }
        return preNode;
    }

    /**
     * 作用: 双向链表反转
     *
     * @param headNode 头节点
     * @return 反转之后的头节点
     */
    public static <T> DoubleLinkedListNode<T> reverse(DoubleLinkedListNode<T> headNode) {

        //0, 设置初始环境
        DoubleLinkedListNode currentNode = headNode;
        DoubleLinkedListNode preNode = currentNode.getPreNode();

        while (currentNode != null) {
            //1, 记录环境
            DoubleLinkedListNode nextNode = currentNode.getNextNode();
            //2, 反转
            currentNode.setPreNode(nextNode);
            currentNode.setNextNode(preNode);
            //3, 设置新环境
            preNode = currentNode;
            currentNode = nextNode;
        }
        return preNode;
    }

    // 单向链表中删除给定值

    /**
     * 作用: 在给定的单向链表中删除给定值
     *
     * @param headNode 给定的链表
     * @param data     要删除的给定值
     * @param <T>      链表data的类型
     * @return 返回删除后的链表
     */
    public static <T> SingleLinkedListNode<T> deleteSpecificValue(SingleLinkedListNode<T> headNode, T data) {
        // 找到第一个不是给定值的节点, 作为头节点
        while (headNode != null) {
            if (!headNode.getData().equals(data)) {
                break;
            }
            headNode = headNode.getNextNode();
        }
        //如果链表中不存在节点了, 直接返回null
        if (headNode == null) {
            return null;
        }
        // 删除后续链表中的指定值
        SingleLinkedListNode currentNode = headNode;
        SingleLinkedListNode nextNode = headNode.getNextNode();
        while (nextNode != null) {
            // 下一个节点的内容是否equals指定值, 是就删除
            if (nextNode.getData().equals(data)) {
                // 删除该nextNode节点, 即将nextNode的nextNode作为currentNode的nextNode
                SingleLinkedListNode newNextNode = nextNode.getNextNode();
                currentNode.setNextNode(newNextNode);
                // 设定新环境
                nextNode = newNextNode;
            } else {
                // 不equals指定值, 就重新设定环境.
                currentNode = nextNode;
                nextNode = nextNode.getNextNode();
            }
        }
        return headNode;
    }

    // 删除双向链表中的指定值
    public static <T> DoubleLinkedListNode<T> deleteSpecificValue(DoubleLinkedListNode<T> headNode, T data) {
        // Step1: 寻找headNode
        while (headNode != null) {
            if (data.equals(headNode.getData())) {
                // 设置环境
                DoubleLinkedListNode nextNode = headNode.getNextNode();
                // gc掉没有用的对象
                headNode.setNextNode(null);
                nextNode.setPreNode(null);
                // 如何换成是下一个headNode
                headNode = nextNode;
            } else {
                break;
            }
        }
        // Step2: 删除后续的指定值
        if (headNode == null) { // 说明链表中空了, 下面的代码不执行了.
            return null;
        }
        DoubleLinkedListNode currentNode = headNode;
        DoubleLinkedListNode nextNode = currentNode.getNextNode();
        while (nextNode != null) {
            //下一个Node是否等于具体值
            if (nextNode.getData().equals(data)) {
                // 是, 删除
                DoubleLinkedListNode newNextNode = nextNode.getNextNode();
                currentNode.setNextNode(newNextNode);
                newNextNode.setPreNode(currentNode);
                //GC
                nextNode.setPreNode(null);
                nextNode.setNextNode(null);
            } else {
                // 不是, 重新设置环境
                currentNode = nextNode;
                nextNode = currentNode.getNextNode();
            }
        }
        return headNode;
    }

    public static void main(String[] args) {
        /*SingleLinkedListNode singleLinkedListNode = generateList();
        System.out.println("-- Before Inversion --");
        printList(singleLinkedListNode);
        singleLinkedListNode = reverse(singleLinkedListNode);
        System.out.println("-- After Inversion --");
        printList(singleLinkedListNode);*/

        SingleLinkedListNode singleLinkedListNode = generateList();
        System.out.println("-- Before Delete --");
        printList(singleLinkedListNode);
        singleLinkedListNode = deleteSpecificValue(singleLinkedListNode, 1);
        System.out.println("-- After Delete --");
        printList(singleLinkedListNode);


    }

    /**
     * 作用: 用于测试, 生成一个单向链表
     *
     * @return 头节点
     */
    private static SingleLinkedListNode generateList() {
        SingleLinkedListNode<Integer> node1 = new SingleLinkedListNode<Integer>(1);
        SingleLinkedListNode<Integer> node2 = new SingleLinkedListNode<Integer>(1);
        SingleLinkedListNode<Integer> node3 = new SingleLinkedListNode<Integer>(2);
        SingleLinkedListNode<Integer> node4 = new SingleLinkedListNode<Integer>(1);
        SingleLinkedListNode<Integer> node5 = new SingleLinkedListNode<Integer>(3);
        SingleLinkedListNode<Integer> node6 = new SingleLinkedListNode<Integer>(1);
        SingleLinkedListNode<Integer> node7 = new SingleLinkedListNode<Integer>(1);

        node1.setNextNode(node2);
        node2.setNextNode(node3);
        node3.setNextNode(node4);
        node4.setNextNode(node5);
        node5.setNextNode(node6);
        node6.setNextNode(node7);
        node7.setNextNode(null);
        return node1;
    }

    /**
     * 作用: 打印单向链表的节点内容
     *
     * @param headNode 头节点
     * @param <T>      节点data类型
     */
    private static <T> void printList(SingleLinkedListNode<T> headNode) {
        SingleLinkedListNode currentNode = headNode;
        while (currentNode != null) {
            System.out.println(currentNode.getData());
            currentNode = currentNode.getNextNode();
        }
    }
}
